\ifx\wholebook\relax \else

\documentclass{article}

\input{../common-en.tex}

\setcounter{page}{1}

\begin{document}

\title{Recursion}

\author{Liu Xinyu
\thanks{{\bfseries Liu Xinyu} \newline
  Email: liuxinyu95@gmail.com}}

\maketitle
\fi

\markboth{Recursion}{Mathematics of Programming}

\ifx\wholebook\relax
\chapter{Recursion}
\numberwithin{Exercise}{chapter}
\fi

\epigraph{GNU means \textbf{G}NU's \textbf{N}ot \textbf{Unix}}{--Richard Stallman}

\begin{wrapfigure}{R}{0.3\textwidth}
 \centering
 \includegraphics[scale=0.4]{img/Pythagoras.eps}
 \captionsetup{labelformat=empty}
 \caption{Pythagoras (about 570BC - 490BC)}
 \label{fig:Pythagoras}
\end{wrapfigure}

People learn the nature with the help of numbers. In the previous chapter, we introduced the Peano axioms and the isomorphisms of natural numbers, like the list data structure in programming. Although we have the natural numbers as the foundamental tool, our building still need some critical corner stones. We use recursive definition without proof of the correctness, like the fraction for example.

\[
\begin{array}{l}
fact(0) = 1 \\
fact(n + 1) = (n + 1) fact(n)
\end{array}
\]

Why does recursion work? what's the theory of recursion? Could the recursion be expressed in some formal way? We'll explore these questions in this chapter.

\section{Everything is number}

Pythagoras is the first mathematician and philosopher who study the universe from numbers. Pythagoras is famous all over the world in the theory named after him. He was born in the island of Samos, off the coast of modern Turkey. Pythagoras might have learnt from Thales of Miletus. With Thales suggestion, he went to Oriental to learn about mathematics. He spent 13 years (22 years in other sayings) in Egypt. After the Persian Empire conquered Egypt, Pythagoras went eastward to Babylon with the army. He learned mathematics and astronomy from the Babylonians. Pythagoras might also arrived in India. Wherever he went, Pythagoras learned from the local scholars to enrich his knowledge. He did not only study hard, but also thought deeply. After long time of learning and studying, Pythagoras formed his own thoughts\cite{HanXueTao16}.

Pythagoras returned his hometown after long journey abroad and began to give lectures. Around 520BC, he left Samos, possibly because he disagreed with the local tyranny. He arrived in the Greek colony of Croton (today's southern Italy). At Croton, he won the trust and admiration of people and founded the philosophical school of Pythagoreanism. Many prominent members of his school were women. The school is devoted to study astronomy, geometry, number theory and music. They are called quadrivium, affecting more than 2000 years of European education\cite{StepanovRose15}. Quadrivium reflects the Pythagoreans' philosophy, everything is number. The planetary motion corresponds to geometry, while geometry is built on top of numbers. Numbers is also connected with music. The so-called Pythagoreans, who were the first to take up mathematics, not only advanced this subject, but saturated with it, they fancied that the principles of mathematics were the principles of all things. said Aristotle in Metaphysics. Pythagoras is the first one discovered the pattern of octiave in mathematics. Pythagoras was revered as the founder of mathematics and music\footnote{There are different sayings about Pythagoras' death. His teachings of dedication and asceticism are credited with aiding in Croton's victory over the neighboring colony. After the victory, a democratic constitution was proposed, but the Pythagoreans rejected it. The supporters of democracy roused the populace against them. An attack was made upon them in some meeting-place. The building was set on fire, and many of the members perished; Different sources disagree regarding whether Pythagoras was killed, or if he managed to flee to Metapontum, where he lived out the rest of his life.}.

The Pythagreans believed all things were made of numbers. They studied the numbers and the their connection to the nature. It developed the early number theory, one of the most important area in mathematics. The pythagreans classified the natural numbers, defined many important concept including even and odd numbers, prime and composite numbers and so on. They found some number equal to the sum of their proper postive divisors\footnote{The proer postive divisors are those positive divisors less than the number}, and named them as perfect numbers. Pythagreans found the first two perfect numbers\footnote{Also known as complete numbers or ideal numbers. Euclid proved a formation rule (Euclid's Element, Book IX, proposition 35) whereby $q(q+1)/2$ is an even perfect number whenever $q$ is a prime of the form $2^p-1$ for prime $p$—what is now called a Mersenne prime. Much later, Euler proved that all even perfect numbers are of this form. This is known as the Euclid–Euler theorem.}. The smallest perfrect number is 6 (6 = 1 + 2 + 3), the next is 28 (28 = 1 + 2 + 4 + 7 + 14). The Pythagorean also found a class of figurate numbers\footnote{The Pythagorean studied mathematics by making figures with small stones. The English word calculus comes from the Greek word stone\cite{HanXueTao16}.}, when they formed geometry figure with stones.

\begin{figure}[htbp]
%\begin{wrapfigure}{R}{0.4\textwidth}
\centering
\begin{tikzpicture}[scale=0.5]
\filldraw (0, 0) circle (0.2);
\draw (0, -1) node{1};
\filldraw (2, 0) circle (0.2)
          (3, 0) circle (0.2)   (3, 1) circle (0.2);
\draw (2.5, -1) node{3};
\filldraw (5, 0) circle (0.2)
          (6, 0) circle (0.2)   (6, 1) circle (0.2)
          (7, 0) circle (0.2)   (7, 1) circle (0.2)   (7, 2) circle (0.2);
\draw (6, -1) node{6};
\filldraw (9, 0) circle (0.2)
          (10, 0) circle (0.2)    (10, 1) circle (0.2)
          (11, 0) circle (0.2)    (11, 1) circle (0.2)    (11, 2) circle (0.2)
          (12, 0) circle (0.2)    (12, 1) circle (0.2)    (12, 2) circle (0.2)    (12, 3) circle (0.2);
\draw (10.5, -1) node{10};
\end{tikzpicture}
\caption{Triangular number}
\label{fig:triangular-num}
%\end{wrapfigure}
\end{figure}

\begin{figure}[htbp]
%\begin{wrapfigure}{R}{0.4\textwidth}
\centering
\begin{tikzpicture}[scale=0.5]
\draw (0, 1) circle (0.2);
\filldraw (0, 0) circle (0.2);
\draw (0, -1) node{2};

\draw (2, 1) circle (0.2)   (2, 2) circle (0.2)
      (3, 2) circle (0.2);
\filldraw (2, 0) circle (0.2)
          (3, 0) circle (0.2)   (3, 1) circle (0.2);
\draw (2.5, -1) node{6};

\draw (5, 1) circle (0.2)   (5, 2) circle (0.2)   (5, 3) circle (0.2)
      (6, 2) circle (0.2)   (6, 3) circle (0.2)
      (7, 3) circle (0.2);
\filldraw (5, 0) circle (0.2)
          (6, 0) circle (0.2)   (6, 1) circle (0.2)
          (7, 0) circle (0.2)   (7, 1) circle (0.2)   (7, 2) circle (0.2);
\draw (6, -1) node{12};

\draw (9, 1) circle (0.2)   (9, 2) circle (0.2)   (9, 3) circle (0.2)   (9, 4) circle (0.2)
      (10, 2) circle (0.2)   (10, 3) circle (0.2)   (10, 4) circle (0.2)
      (11, 3) circle (0.2)   (11, 4) circle (0.2)
      (12, 4) circle (0.2);
\filldraw (9, 0) circle (0.2)
          (10, 0) circle (0.2)    (10, 1) circle (0.2)
          (11, 0) circle (0.2)    (11, 1) circle (0.2)    (11, 2) circle (0.2)
          (12, 0) circle (0.2)    (12, 1) circle (0.2)    (12, 2) circle (0.2)    (12, 3) circle (0.2);
\draw (10.5, -1) node{20};
\end{tikzpicture}
\caption{Oblong number (number of rectangle)}
\label{fig:oblong-num}
%\end{wrapfigure}
\end{figure}

Figure \ref{fig:triangular-num} and \ref{fig:oblong-num} demonstrate the triangular numbers and oblong numbers (rectangle numbers). It's easy to figure out that the oblong number is two times of the corresponding triangle number. While the triangle number is the sum of the first $n$ postive integers. By this way, the Pythagoreans found the formula to calculate the sum of postive integers.

\[
1 + 2 + 3 + ... + n = \frac{1}{2}n(n+1)
\]

The Pythagoreans also observed that the odd number could be represented in gnomon shape as shown in figure \ref{fig:gnomon-num}. And the first $n$ gnome shapes form a square, as in figure \ref{fig:square-num}. By this way, they found the formula to calculate the sum of $n$-odd numbers.

\[
1 + 3 + 5 + ... + (2n - 1) = n^2
\]

\begin{figure}[htbp]
%\begin{wrapfigure}{R}{0.4\textwidth}
\centering
\begin{tikzpicture}[scale=0.5]
\filldraw (0, 0) circle (0.2);
\draw (0, -1) node{1};

\draw (2, 1) circle (0.2)
      (3, 0) circle (0.2)   (3, 1) circle (0.2);
\draw (2.5, -1) node{3};

\filldraw (5, 2) circle (0.2)   (6, 2) circle (0.2)   (7, 2) circle (0.2)
          (7, 0) circle (0.2)   (7, 1) circle (0.2);
\draw (6, -1) node{5};

\draw (9, 3) circle (0.2)   (10, 3) circle (0.2)   (11, 3) circle (0.2)   (12, 3) circle (0.2)
      (12, 0) circle (0.2)    (12, 1) circle (0.2)    (12, 2) circle (0.2);
\draw (10.5, -1) node{7};
\end{tikzpicture}
\caption{Gnomon number}
\label{fig:gnomon-num}
%\end{wrapfigure}
\end{figure}

\begin{figure}[htbp]
%\begin{wrapfigure}{R}{0.4\textwidth}
\centering
\begin{tikzpicture}[scale=0.5]
\filldraw (0, 0) circle (0.2);
\draw (0, -1) node{1};

\filldraw (2, 0) circle (0.2);
\draw (2, 1) circle (0.2)
      (3, 0) circle (0.2)   (3, 1) circle (0.2);
\draw (2.5, -1) node{4};

\filldraw (5, 0) circle (0.2);
\draw (5, 1) circle (0.2)
      (6, 0) circle (0.2)   (6, 1) circle (0.2);
\filldraw (5, 2) circle (0.2)   (6, 2) circle (0.2)   (7, 2) circle (0.2)
          (7, 0) circle (0.2)   (7, 1) circle (0.2);
\draw (6, -1) node{9};

\filldraw (9, 0) circle (0.2);
\draw (9, 1) circle (0.2)
      (10, 0) circle (0.2)   (10, 1) circle (0.2);
\filldraw (9, 2) circle (0.2)   (10, 2) circle (0.2)   (11, 2) circle (0.2)
          (11, 0) circle (0.2)   (11, 1) circle (0.2);
\draw (9, 3) circle (0.2)   (10, 3) circle (0.2)   (11, 3) circle (0.2)   (12, 3) circle (0.2)
      (12, 0) circle (0.2)    (12, 1) circle (0.2)    (12, 2) circle (0.2);
\draw (10.5, -1) node{16};
\end{tikzpicture}
\caption{Square number and gnomon numbers}
\label{fig:square-num}
%\end{wrapfigure}
\end{figure}

This is the answer to the exercise problem in chapter 1. With these facts, the Pythagreans found there were many things can be explained with numbers. Given two strings under the same tension, it's said Pythagras found the tune is harmonic if the ratio of their lengths is integer. He developed the earlist music theory based on this. It seemed that music and mathematics are totally different things, while finally Pythagoras concluded that music was mathematics. Such unexpected relationship impacted Pythagoras greatly. He guess that all things can be explained with integers or the ratio of integers. The Pythagoreans started to finding more and more things connected to nunbers, they believed the meaning of the whole universe is the harmonic of numbers, and developed the phylosophy based on number. This led to the attempt to build the geometry also on top of the numbers, so the overall mathematics is based on integers.

The Pythagoreans' most famous achievement is the Pythagoras theorem. However, we'll see later, this theorem is a double-edged sward, it leads to a recursive circle, and reveals the loophole of the idea that everything is number. In order to understand this, we need introduce the concept of commensurable and the Euclidean algorithm. To build the geometry on top of the numbers, The Pythagorean defined how to measure a line segment with another, if segment A can be represented by duplicating segment V finite times, we say V can measure A. It means the length of one segment is the integer times of the other. Altough we can use varies of measurements, when use the same segment to measure different ones, it has to be the common measure. That is to say if and only if segment V can measure both A and B, it is the common measure of them. The Pythagoreans believed for any two segments, there must be a common measure. If this was true, then the whole geometry can be built on integers.

%\begin{wrapfigure}{R}{0.4\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.2]{img/Pythagoras-proof.eps}
 \caption{One of the methods to prove the Pythagoras theorem. The areas in white are same.）}
 \label{fig:Pythagoras-proof}
\end{figure}
%\end{wrapfigure}

\section{The Euclidean algorithm}

As there can be mutliple common measures, we define the biggest one as the greatest common measure. Formally speaking, if segment V is the common measure of A and B, and V is greater than any other common measure, we say V is the greatest common measure of A and B. Given two segments, how to find the greatest common measure? There is a famous acient recursive method, called the Euclidean algorithm to solve this problem. It named after the great ancient Greek methematician Euclid\footnote{The Euclidean algorithm was also developed independently in ancient India and China. The Indian methematician Aryabhata used this method to solve the Diophantine equation around the end of the 5th centry. The Euclidean algorithm was treated as a special case of the Chinese remainder theorem in {\em Sunzi Suanjing}. In 1247, Qin Jiushao gave the detailed algorithm in his Mathematical Treatise in Nine Sections (Shushu Jiuzhang).}. This algorithm is defined as proposition 3, in book X\footnote{The same algorithm for integers is also defined as propostion 1, book VII. However, the algorithm for segements covers the integer case.} of Euclid's Elements\cite{Elements}.

\subsection{The Euclid's Elements}

\begin{wrapfigure}{R}{0.4\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.6]{img/Euclid.eps}
 \captionsetup{labelformat=empty}
 \caption{Euclid, About 300BC}
 \label{fig:Euclid}
%\end{figure}
\end{wrapfigure}

Euclid of Alexandria is the most prominent ancient Greek mathematican, often referred to as ``father of geometry''. His {\em Elements} is one of the most influential works in the history of mathematics. However, little is known of Euclid's life except that he taught at Alexandria in Egypt. The year and place of both his birth and death are unknown. Proclus, the last major Greek philosopher who lived around 450AD introduced Euclid briefly in his {\em Commentary on the Elements}. He mentioned a interesting story about Euclid. When Ptolemy I of Alexandria (ruler of Egypt 323BC - 283BC) grew frustrated at the degree of effort required to master geometry via Eculid's {\em Elements}, he asked if there was a shorter path, Euclid replied there is no royal road to geometry. This becomes the learning maxim of eternal. Another story told by Stobaeus said someone who had begun to learn geometry with Euclid, when he had learnt the first theorem, asked Euclid "What shall I get by learning these things?" Euclid said "Give him threepence since he must make gain out of what he learns". Euclid disagree with the narrow practical view of learning\cite{Elements}.

From ancient times to the late 19th century, people considered the {\em Elements} as a perfect example of correct reasoning. Although many of the results in {\em Elements} originated with earlier mathematicians, one of Euclid's accomplishments was to present them in a single, logically coherent framework, making it easy to use and easy to reference, including a system of rigorous mathematical proofs that remains the basis of mathematics 23 centuries later. More than a thousand editions have been published, making it one of the most popular books after the Bible. Even today, {\em Elements} is still widely taught in school\footnote{The most popular version is edited by the French mathematician Lagrange (1736 - 1813).} as one of the basic way to train logic reasoning\cite{HanXueTao16}.

\subsection{Euclidean algorithm}

\begin{proposition}[Elements, Book X, Proposition 3]
Given two commensurable quantities, find the greatest common measure.
\end{proposition}

The solution Euclid gave only uses recursion and subtraction. It means the greatest common measure can be solved only with ruler and compass essentially. This algorithm can be formalized as the following\footnote{Term 'gcm' is the abbreviation for the greatest common measure. When $a$ and $b$ are integers, we often use gcd as the abbreviation for the greatest common divisor.}.

\be
gcm(a, b) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  a = b & a \\
  b < a & gcm(a - b, b) \\
  a < b & gcm(a, b - a)
  \end{array}
\right.
\label{eq:gcm-minus}
\ee

Suppose segement $a$ and $b$ are comensurable. If they are equal, then either one is the greatest common measure, we can return $a$ as the result. If $a$ is longer than $b$, we can use compass to intercept $b$ from $a$ repeatedly (through recursion), then find the greatest common measure for the intercepted segment $a'$ and $b$; otherwise if $b$ is longer than $a$, we intercept $a$ from $b$ repeatedly, and find the greatest common measure for the segment $a$ and $b'$. Figure \ref{fig:line-seg-gcm} illustrated the steps when processing two segments. We can also use this algorithm to process two integers 42 and 30. The detailed steps is as the following table.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.15]

\filldraw (0, 0) circle (0.5)   (30, 0) circle (0.5)   (42, 0) circle (0.5);
\draw (-8, 0) node{$a$} (0, 0) -- (42, 0);
\filldraw (0, -5) circle (0.5)   (30, -5) circle (0.5);
\draw (-8, -5) node{$b$} (0, -5) -- (30, -5);

\filldraw (0,  -15) circle (0.5)   (12, -15) circle (0.5);
\draw (-8, -15) node{$a'=a-b$} (0, -15) -- (12, -15);
\filldraw (0, -20) circle (0.5)   (12, -20) circle (0.5)   (24, -20) circle (0.5)   (30, -20) circle (0.5);
\draw (-8, -20) node{$b$} (0, -20) -- (30, -20);

\filldraw (0,  -30) circle (0.5)   (6, -30) circle (0.5)   (12, -30) circle (0.5);
\draw (-8, -30) node{$a'$} (0, -30) -- (12, -30);
\filldraw (0, -35) circle (0.5)   (6, -35) circle (0.5);
\draw (-8, -35) node{$b'=b-2a'$} (0, -35) -- (6, -35);

\filldraw (0,  -45) circle (0.5)   (6, -45) circle (0.5);
\draw (-8, -45) node{$a''=a'-b'$} (0, -45) -- (6, -45);
\filldraw (0, -50) circle (0.5)   (6, -50) circle (0.5);
\draw (-8, -50) node{$b'$} (0, -50) -- (6, -50);

\end{tikzpicture}
\caption{Euclidean algorithm example steps.}
\label{fig:line-seg-gcm}
\end{figure}

\begin{tabular}{|l|l|l|}
\hline
$gcm(a, b)$ & $a$ & $b$ \\
\hline
$gcm(42, 30)$ & 42 & 30 \\
\hline
$gcm(12, 30)$ & 12 & 30 \\
\hline
$gcm(12, 18)$ & 12 & 18 \\
\hline
$gcm(12, 6)$ & 12 & 6 \\
\hline
$gcm(6, 6)$ & 6 & 6 \\
\hline
\end{tabular}

Repeatedly subtracting $b$ from $a$ to get $a'$, it's exactly the definition of division with remainder: $a' = a - \lfloor a / b \rfloor$, or denoted as $a'= a \bmod b$. We can use the division with remainder to replace the repeated subtraction in the origin Euclidean algorithm. Besides that, when one quantity is an integeral multiple of the other, for example $b \leq a$ and $a$ can be divided by $b$, we know the greatest common measure is $b$. As the remainder $a \bmod b = 0$, we define $gcm(0, b) = gcm(b, 0) = b$. We can compare $a$ and $b$ first and exchange them if $a < b$. As we know $a \bmod b$ must be less than $b$, when next time do the recursive computation, we can directly exchange them as $gcm(b, a \bmod b)$. This gives the improved Euclidean algorithm.

\be
gcm(a, b) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  b = 0 & a\\
  \text{otherwise} & gcm(b, a \bmod b) \\
  \end{array}
\right.
\label{eq:gcm}
\ee

Why does this algorithm give the greatest common measure? We need prove it with two steps. At step one, we prove this algorithm gives the common measure. Suppose $b \leq a$, let the integer $q_0$ be the quotient, $r_0$ be the remainder. We have $a = b q_0 + r_0$. As we get the common measure if $r_0$ is zero, let's focus on the case that $r_0$ is not zero. We can next express $b$ as $b = r_0 q_1 + r_1$, and list the similar equations unless the remainder is zero.

\[
\begin{array}{rcl}
a &=& b q_0 + r_0 \\
b &=& r_0 q_1 + r_1 \\
r_0 &=& r_1 q_2 + r_2 \\
r_1 &=& r_2 q_3 + r_3 \\
& & ...
\end{array}
\]

As long as $a$ and $b$ are commensurable, this list is not infinite. This is because every time, we use compass to intercept integral times, the quotients are integers. And the remainders are less than the divisor. We have $b > r_0 > r_1 > r_2 > ... > 0$. As the remainder can not less than zero, and the initial quantity is finite, we must reach to $r_{n-2} = r_{n-1} q_n$ within finite steps.

Next is to prove $r_{n-1}$ can measure both $a$ and $b$. Obviously $r_{n-1}$ measures $r_{n-2}$ by definition. Consider the last second equation $r_{n-3} = r_{n-2} q_{n-1} + r_{n-1}$, since $r_{n-1}$ measures $r_{n-2}$, $r_{n-1}$ also measures $r_{n-2} q_{n-1}$. So it measures $r_{n-2} q_{n-1} + r_{n-1}$, which equals to $r_{n-3}$. Similiarily, we can prove $r_{n-1}$ measures the left hand of every equations step by step up, till $b$ and $a$. This proves the answer found by Euclidean algorithm, $r_{n-1}$ is the common measure of $a$ and $b$. Suppose the greatest common measure is $g$, we have $r_{n-1} \leq g$.

The next step is to prove, for any common measure $c$ for $a$ and $b$, it measures $r_{n-1}$. As $c$ is the common measure, both $a$ and $b$ can be expressed with it, let $a = mc$, $b = nc$, where $m$ and $n$ are some integers. Then the first equation $a = b q_0 + r_0$ can be denoted as $mc = ncq_0 + r_0$, as we know $r_0 = (m - nq_0)c$, it means $c$ measures $r_0$. Similarily, we can prove $c$ measures $r_1$, $r_2$, ..., $r_{n-1}$ one by one. Thus we proved any common measure also measures $r_{n-1}$, so the greatest one $g$ also measures $r_{n-1}$. It means $g \leq r_{n-1}$.

Combine the results from step one and two, that $r_{n-1} \leq g$ and $g \leq r_{n-1}$, we deduced the greatest common measure $g = r_{n-1}$. It does not only proved the correctness of Euclidean algorithm, but also tells us $g$ is the greatest common measure for every pair of quantities:

\be
g = gcm(a, b) = gcm(b, r_0) = ... = gcm(r_{n-2}, r_{n-1}) = r_{n-1}
\label{eq:recursive-gcm}
\ee

\subsection{Extended Euclidean algorithm}

\begin{wrapfigure}{R}{0.4\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.5]{img/Bezout.eps}
 \captionsetup{labelformat=empty}
 \caption{Étienne Bézout, 1730 - 1783}
 \label{fig:Bezout}
%\end{figure}
\end{wrapfigure}

The extended Euclidean algorithm is an extension to the Euclidean algorithm. For the given quantity $a$ and $b$, in addition to compute the greatest common measure $g$, it also find two integers $x$ and $y$, that satisfy Bézout's identity $ax + by = g$. Why does Bézout's identity\footnote{Bézout's identity, or Bézout's theorem was first found and proven by French mathematician Méziriac (Claude Gaspard Bachet de Méziriac，1581–1638) for integers. Bézout proved it hold for polynomials. Bézout identity can be extended to any Euclidean domain and Principle Idean Domain (PID).} always hold? Below is one of the methods to prove it. We can construct a set, consists of all the positive linear combinations of $a$ and $b$.

\[
S = \{ ax + by | x, y \in \mathbb{Z}\ \text{and} \ ax + by > 0\}
\]

For line segments, $S$ must not be empty, as it at least contains $a$ (where $x = 1, y = 0$) and $b$ (where $x = 0, y = 1$). Since all the elements in $S$ are positive, there must exist the smallest one. We denote the smallest element as $g = as + bt$. We'll next show that $g$ is the greatest common measure of $a$ and $b$. Let's express $a$ as the quotient and remainder of $g$.

\be
a = qg + r
\label{eq:Euclidean-division}
\ee

Where the remainder $0 \leq r < g$. It is either zero or belongs to set $S$, this is because the following.

\[
\begin{array}{rll}
r & = a - qg & \text{From (\ref{eq:Euclidean-division})} \\
  & = a - q(as + bt) & \text{Definition of}\ g \\
  & = a(1 - qs) - bqt & \text{Change to combination of}\ a\ \text{and}\ b
\end{array}
\]

It means $r$ can be expressed as the linear combination of $a$ and $b$, therefore, if it's not zero, it must belong to set $S$. However, this is not possible because we previously defined $g$ as the least postive element in $S$, while $r$ is less than $g$. To avoid this contradition, we know that $r$ has to be zero. from equation (\ref{eq:Euclidean-division}), $g$ measures $a$. With the same method, we can prove $g$ also measures $b$. Therefore $g$ is the common measure of them. We'll next prove that $g$ is the greatest one. Consider an arbitrary common measure $c$ for $a$ and $b$, according to the definition, there exists integers $m$ and $n$, that $a = mc$ and $b = nc$. Then $g$ can be expressed as:

\[
\begin{array}{rll}
g & = as + bt & \text{The definition} \\
  & = mcs + nct & \text{$c$ is common measure of $a$ and $b$} \\
  & = c(ms + nt) & \text{$g$ is multiple of $c$}
\end{array}
\]

It means $c$ measure $g$, so $c \leq g$. It gives that $g$ is the greatest common measure. Summarize the above, we complete the proof of Bézout's identity. There exists integers, that $ax + by = g$ holds. Besides that, we know the greatest common measure is the minimum postive values among all the linear combinations.

%\begin{wrapfigure}{R}{0.4\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.8]{img/Meziriac.eps}
 \captionsetup{labelformat=empty}
 \caption{Claude Gaspard Bachet de Méziriac, 1581–1638, who first discovered and proved Bézout's idendity for integers.}
 \label{fig:Meziriac}
\end{figure}
%\end{wrapfigure}

We can deduce the extended Euclid algorithm with Bézout's idendity.

\[
\begin{array}{rlr}
ax + by & = gcm(a, b) & \text{Bézout's idendity} \\
        & = gcm(b, r_0) & \text{Euclid algorithm (\ref{eq:recursive-gcm})} \\
        & = bx' + r_0 y' & \text{Use Bézout's idendity for $b$ and $r_0$} \\
        & = bx' + (a - bq_0)y' & \text{By $a = b q_0 + r_0$} \\
        & = ay' + b(x' - y'q_0) & \text{As linear combination of $a$ and $b$} \\
        & = ay' + b(x' - y' \lfloor a / b \rfloor) & \text{$q_0$ as the quotient of $a$ and $b$}
\end{array}
\]

This gives the recursion case:

\[
\left \{
  \begin{array}{l}
  x = y' \\
  y = x' - y' \lfloor a / b \rfloor
  \end{array}
\right.
\]

The edge case happends when $b = 0$, we have $gcm(a, 0) = 1a + 0b$. Combine it with the recursive case, gives the extended Euclid algorithm.

\be
gcm_{ex}(a, b) = \left \{
  \begin{array}
  {r@{\quad:\quad}l}
  b = 0 & (a, 1, 0) \\
  \text{otherwise} & \begin{array}{l}
                (g, y', x' - y' \lfloor a / b \rfloor) \\[2pt]
                \text{其中}(g, x', y') = gcm_{ex}(b, a \bmod b)
                \end{array} \\
  \end{array}
\right.
\label{eq:gcm-ext}
\ee

As an example, here is a puzzle can be solved with the extended Euclid algorithm(\cite{LiuXinyu2017}, p50). Given two jars with capacity of 9 and 4 gallons, how to get 4 gallons from the river?

There are some variances of this puzzle. The capacities can be other nunmbers. It's said the French mathematician Poisson (Sim\`{e}on Denis Poisson) solved this puzzle when he was a kid.

There are total six operations between two jars. Denote the big one as $A$, its capacity is $a$; denote the small one as $B$ with capacity $b$:

\begin{itemize}
\item Fill the big jar $A$;
\item Fill the small jar $B$;
\item Empty the big jar $A$;
\item Empty the small jar $B$;
\item Pour the water from jar $A$ to $B$;
\item Pour the warer from jar $B$ to jar $A$.
\end{itemize}

The last two operation stop when either jar is empty or filled. Below example shows a list of operations (suppose $b < a  2b$ hold).

\begin{table}[htbp]
\centering
\begin{tabular}{l|l|l}
$A$ & $B$ & Operation \\
\hline
0 & 0 & start \\
0 & b & fill $B$ \\
b & 0 & pour from $B$ to $A$ \\
b & b & fill $B$ \\
a & 2b - a & pour from $B$ to $A$ \\
0 & 2b - a & empty $A$ \\
2b - a & 0 & pour from $B$ to $A$ \\
2b - a & b & fill $B$ \\
a & 3b - 2a & pour from $B$ to $A$ \\
... & ... & ... \\
\end{tabular}
\caption{The water in the jars and the operations.} \label{tab:jug-ops}
\end{table}

No matter what sequence of operations, the water in the jars can always be expressed as $ax + by$ where $x$ and $y$ are integers. It means the water we get is the linear combination of $a$ and $b$. From the proof of Bézout's identity, we know the smallest positive number of this linear combination is exactly the greatest common measure $g$. We can tell it is possible to get $c$ gallon water if and only if $c$ can be measured by $g$\footnote{If and only if $c$ can be devided by the greatest common divisor $g$ for integer capacities.}. We assume $c$ is not greater than the capacity of the bigger jar.

For example, we can't get 5 gallons of water with two jars of 4 gallons and 6 gallons. This is because the greatest common divisor of 4 and 6 is 2. Which can't divides 5. (In other words, we can't get odd galons of water with two jars of even gallons capacities.) If $a$ and $b$ are coprime, i.e. $gcd(a, b) = 1$, then we are sure to get any natural number $c$ gallons of water.

Although we can tell the puzzle is solvable if $g$ measures $c$, we still don't know the steps to pour the water. Actually, the steps can be decuded as far as we can find two integers $x$ and $y$, satisfying $ax + by = c$. If $x > 0, y < 0$, it means we need fill jar $A$ $x$ times, and empty jar $B$ $y$ times; Else if $x < 0, y > 0$, we need empty jar $A$ $x$ times, and fill jar $B$ $y$ times.

For instance, let the capacity of the big jar $a = 5$ gallon, the small jar $b = 3$ gallon. We want to get $c=4$ gallons of water. As $4 = 3 \times 3 - 5$, so $x = -1, y = 3$. We can arrange the steps as below.

\begin{table}[htbp]
\centering
\begin{tabular}{l|l|l}
$A$ & $B$ & operation \\
\hline
0 & 0 & start \\
0 & 3 & fill $B$ \\
3 & 0 & pour from $B$ to $A$ \\
3 & 3 & fill $B$ \\
5 & 1 & pour from $B$ to $A$ \\
0 & 1 & empty $A$ \\
1 & 0 & pour from $B$ to $A$ \\
1 & 3 & fill $B$ \\
4 & 0 & pour from $B$ to $A$ \\
\end{tabular}
\caption{Steps to get 4 gallons of water.} \label{tab:designed-jugs-ops}
\end{table}

We can see from these steps, jar $B$ is filled 3 times, jar $A$ is emptied 1 time. The next question is how to find $x$ and $y$ that satisfies $ax + by = c$. With the extended Euclid algorithm, we can find a solution to Bézout's identity $ax_0 + by_0 = g$. Since $c$ is $m$ times of the greatest common measure $g$, we can make a solution by multiplying $x_0$ and $y_0$ $m$ times.

\[
\begin{cases}
  x_1 = x_0 \dfrac{c}{g} \\[2ex]
  y_1 = y_0 \dfrac{c}{g}
\end{cases}
\]

From this solution, we can have all the integer solutions to the Diophantus equation{Naming after the acient Greek mathematician, Diophantus of Alexandira (about 200 - 284AD). In his book \textit{Arithmetica}, he made important advances in mathematical notation, becoming the first person known to use algebraic notation and symbolism. Diophantus is often called “the father of algebra" because he contributed greatly to number theory, mathematical notation, and because \textit{Arithmetica} contains the earliest known use of syncopated notation\cite{HanXueTao2009}.}.

\be
\begin{cases}
  x = x_1 - k \dfrac{b}{g} \\[2ex]
  y = y_1 + k \dfrac{a}{g}
\end{cases}
\ee

Where $k$ is an integer number. Thus we achieve all the integer solutions to the water jar puzzle. Further, we can find a special $k$, which minimizes $|x| + |y|$, it gives the fast pouring steps\footnote{One way to get this special $k$ is to represent the solution as two lines in Cartesian plain. When taking absoluted value, it flips the lower part to the x-axis. Then we can find the $k$ minimizes $|x| + |y|$ from the figure.}. Below is the example Haskell program solves this  puzzle.

\lstset{frame=single}
\begin{lstlisting}
import Data.List
import Data.Function (on)

-- Extended Euclidean Algorithm
gcmex a 0 = (a, 1, 0)
gcmex a b = (g, y', x' - y' * (a `div` b)) where
  (g, x', y') = gcmex b (a `mod` b)

-- Solve the linear Diophantine equation ax + by = c
solve a b c | c `mod` g /= 0 = (0, 0, 0, 0) -- no solution
            | otherwise = (x1, u, y1, v)
  where
    (g, x0, y0) = gcmex a b
    (x1, y1) = (x0 * c `div` g, y0 * c `div` g)
    (u, v) = (b `div` g, a `div` g)

-- Optimal by minimize |x| + |y|
jars a b c = (x, y) where
  (x1, u, y1, v) = solve a b c
  x = x1 - k * u
  y = y1 + k * v
  k = minimumBy (compare `on` (\i -> abs (x1 - i * u) +
                                     abs (y1 + i * v))) [-m..m]
  m = max (abs x1 `div` u) (abs y1 `div` v)
\end{lstlisting}

After figure out $x$ and $y$, we can populate the steps as in Appendix.

\subsection{Influence of Euclid algorithm}

在“万物皆数”的哲学思想下，虽然欧几里得算法最初是为了寻找两个整数的最大公约数而产生的。但是经过欧几里得之手，算法却应用到了抽象的几何量上。从整数的最大公约数，到可公度量的最大公度，我们看到了几何量和数的分离\footnote{这也是我们使用gcm，而没有使用更常见的gcd作为算法简写的原因。}。几何不仅没有建立在整数之上，反而独立发展，解决了整数之外的问题。以至于后来古希腊数学形成了这样的传统，任何关于数的结论，都需要给出几何的证明。这一传统直到十六世纪仍然影响着人们。意大利数学家卡尔丹（Gerolamo Cardano）\footnote{也译作卡尔达诺}在关于解三次、四次方程的著作《大术》（Ars Magna，1545年出版）中，仍然使用类似立方体填补法的几何论证\cite{HanXueTao2009}。

欧几里得算法是最著名的一个递归算法。德国数学家，解析数论创始人狄利克雷（Dirchlet）在他的著作《数论讲义》中评价到：“整个数论的结构都建立在同一个基础之上，这个基础就是最大公约数算法。”现代密码学的RSA加密算法\footnote{RSA算法是最早的一种公开密钥加密的非对称加密算法，RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。}直接使用了扩展欧几里得算法。我们在上一节通过一道趣题展示了如何使用扩展欧几里得算法给出二元线性不定方程$ax + by = c$的整数解。具体来说，就是先求出最大公度$g$，并判断$g$是否整除$c$，若不能，则无整数解。否则，将满足贝祖等式的$x_0$，$y_0$，扩大$c/g$倍得到一组特解$x_1$、$y_1$。然后得到一般二元线性不定的通解$x = x_1 - k b / g$和$y = y_1 + k a / g$。

\begin{wrapfigure}{R}{0.4\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.25]{img/Hippasus.eps}
 \captionsetup{labelformat=empty}
 \caption{希帕索思（Hippasus of Metapontum）约公元前五世纪。}
 \label{fig:Hippasus}
%\end{figure}
\end{wrapfigure}

欧几里得算法是一把锋利的宝剑，但是它强大的递归原理被反过来指向了“万物皆数”的基石——万物可公度。一切事物和现象都可以归结为整数与整数的比。从而引发了毕达哥拉斯学派哲学思想的危机。约公元前470年左右，毕达哥拉斯学派的学生希帕索思试图寻找正方形的对角线和边的公度。经过仔细思考他发现不管度量单位取得多么小，这两条线段都无法公度。还有的说法是希帕索思从毕达哥拉斯学派的神秘五角星标志上得到了启发。毕达哥拉斯学派成员用五角星作为学派的徽章和联络标志。有一则故事说，学派的一个成员流落异乡，贫病交迫，无力酬谢房主的款待，临终前要房主在门上画一个五角星。若干年后，有同派的人看到这个标志，询问事情的经过，厚报房主而去\cite{HanXueTao16}。美国迪士尼在1959年的动画片《唐老鸭漫游数学奇境》中，描绘了唐老鸭遇到了毕达哥拉斯和他的朋友们，在了解音乐、艺术与数的关系后，唐老鸭的手掌上也画上了神秘的五角星。如图\ref{fig:pentagram}所示，传说希帕索思发现线段AC和AG也是无法公度的。

%《唐老鸭漫游数学奇境》（Donald In Mathmagic Land ）

%\begin{wrapfigure}{L}{0.4\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.5]{img/pentagram.eps}
 %\captionsetup{labelformat=empty}
 \caption{递归的五角星}
 \label{fig:pentagram}
\end{figure}
%\end{wrapfigure}

十九世纪的苏格兰数学家乔治$\cdot$克里斯托重建了希帕索思的证明。使用反证法，假设存在一条单位线段$c$能够公度正方形的边和对角线。根据度量的定义，可以令边长为$mc$、对角线长为$nc$，其中$m$、$n$都是正整数。如图\ref{fig:irrational}所示，我们以点A为圆心，以边长为半径做圆弧交对角线AC于点E。然后从E出发作垂直与对角线的直线，并交边BC于点F。

%\begin{wrapfigure}{L}{0.4\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=2]{img/irrational.eps}
 %\captionsetup{labelformat=empty}
 \caption{正方形的边长和对角线}
 \label{fig:irrational}
\end{figure}
%\end{wrapfigure}

根据圆的定义，线段AE的长度等于正方形的边长，所以线段EC的长度等于$(m - n)c$。因为EF垂直于AC，而角$\angle ECF$是$45\degree$，故三角形ECF是等腰直角三角形。由于等腰三角形两腰相等，故而有$|EC| = |EF|$。接下来我们注意两个直角三角形$\triangle AEF$和$\triangle ABF$，由于边AE等于AB，同时AF是公共边，因此两个直角三角形全等。这样就得到边$|EF| = |FB|$。综合下来，我们有$|EC| = |EF| = |FB|$。这样线段FB的长度也等于$(m - n)c$，所以线段CF的长度等于CB的长度减去FB的长度，等于$nc - (m - n)c = (2n - m)c$。我们把得到的结论列在下面。

\[
\begin{array}{c|c}
\begin{cases}
|AC| = mc \\
|AB| = nc
\end{cases} &
\begin{cases}
|CF| = (2n - m)c \\
|CE| = (m - n)c
\end{cases} \\[4ex]
\text{大正方形} & \text{小正方形}
\end{array}
\]

由于$m$、$n$都是正整数，显然$c$也可以公度小正方形的对角线$CF$和边$CE$。仿照上面的方法，我们可以继续作出更小的正方形，并且重复作出无穷无尽的更小的正方形。而$c$总可以公度每一个小正方形的斜边和对角线。由于$m$、$n$是有限的正整数，这一过程不可能无限做下去，这样就产生了矛盾。于是我们一开始的假设不成立，即正方形的边和对角线不可公度。

这样毕达哥拉斯万物皆数的理论就出现了一个漏洞：存在线段的长度无法用整数比进行度量。据说希帕索思因为这个发现，而遭到谋杀，毕达哥拉斯学派担心这个秘密被泄露出去，而把希帕索思沉入大海。然而历史的车轮不会倒退，古希腊的哲学家和数学家们正视了这个问题，经过欧多克索斯、亚里士多德和欧几里得等人的工作，终于严格定义了不可公度和无理量，并通过几何将它们纳入了古希腊的数学体系。

\begin{proposition}[《几何原本》，卷十，命题二]
如果从两个不等量的大量中连续减去小量，直到余量小于小量，再从小量中连续减去余量直到小于余量，这样一直作下去，当所余的量总不能量尽它前面的量时，则称两个量不可公度。
\end{proposition}

这里出现了一个有趣的现象，不可公度是用欧几里得算法能否停止来定义的。由于欧几里得算法是递归的，也就是说递归能否中止成了判断条件。这再次将我们的注意力引入到递归的本质上。递归究竟是什么？它怎样用形式化的方法表示？

\begin{Exercise}
\Question{我们给出的欧几里得算法是递归的，请消除递归，只使用循环实现欧几里得算法和扩展欧几里得算法。}
\Question{大多数编程环境中的取模运算，要求除数、被除数都是整数。但是线段的长度不一定是整数，请实现一个针对线段的取摸运算。它的效率如何？}
\Question{我们在证明欧几里得算法正确性的过程中说：“每次都保证余数小于除数。即$b > r_0 > r_1 > r_2 > ... > 0$，但是余数不可能小于零。由于起始值是有限的，故最终算法一定中止。”为什么不会出现，$r_{n}$无限接近于零但不等于零的情况？算法一定会中止么？$a$和$b$是可公度的这一前提保证了什么？}
\Question{对于二元线性不定方程$ax + by = c$，若$x_1$、$y_1$和$x_2$、$y_2$为两对整数解。试证明$|x_1 - x_2|$的最小值为$b/gcm(a, b)$，且$|y_1 - y_2|$的最小值为$a/gcm(a, b)$。}
\Question{试证明图\ref{fig:pentagram}的五角星中的线段AC和AG是不可公度的。使用实数表示，它们比值是什么？}
\end{Exercise}

\section{$\lambda$演算}

如果进行计算的是如我们人类这样的智慧生命，也许不用深究递归的原理。我们只需要进行计算，发现递归时就在自己的思维中螺旋进入下一个层次。当递归终止时，就退回上一层。当人们思考如何用机器帮助我们进行计算时，这一问题才变得重要起来。二十世纪三十年代，当人们在研究可计算问题时，分别独立提出了一些计算模型。最著名的包括图灵提出的图灵机模型（1935年），丘奇（1932到1941年）和克莱尼（Stephen Kleene，1935年）提出的$\lambda$演算，埃尔布朗（Jacques Herbrand）和哥德尔（Kurt Gödel）提出的递归函数（1934年）等。

%\begin{wrapfigure}{L}{0.35\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.2]{img/Turing.eps}
 \captionsetup{labelformat=empty}
 \caption{艾伦$\cdot$图灵（Alan Mathison Turing，1912 - 1954）}
 \label{fig:Turing}
\end{figure}
%\end{wrapfigure}

图灵是英国数学家、逻辑学家，深刻地影响了计算机科学的理论发展，他提出使用图灵机来形式化算法和计算的概念，是现代通用计算机的模型。图灵因此被称为计算机科学之父和人工智能之父\cite{wiki-Turing}。第二次世界大战期间，图灵参加了盟军位于布莱切利公园的密码破译中心。他设计了很多技术用以快速破解纳粹德国的密码。图灵研制了一台绰号为“炸弹”（Bombe）的电子机器，使用战前波兰发现的方法，可以在一小时内找到德军恩尼格玛（Enigma）密码机的密钥。密码的成功破译是盟国获胜的一个关键因素，许多历史学家认为缩短了战争达2年之多，并且挽救了成千上万的生命。战争结束后，图灵开始从事“自动计算机”(ACE)的逻辑设计和具体研制工作。在图灵的设计思想指导下，1950年制出了ACE样机，1958年制成大型ACE机。人们认为，通用计算机的概念就是图灵提出来的。1950年，图灵开始考虑机器思维的问题并在论文《计算机与智能》中提出了著名的“图灵测试”。这一划时代的作品，使图灵赢得了“人工智能之父”的桂冠。1951年，由于在可计算数学方面所取得的成就，图灵成为英国皇家学会会员，时年39岁。为了纪念他对计算机科学的巨大贡献，由美国计算机协会（ACM）于1966年设立一年一度的图灵奖，以表彰在计算机科学中做出突出贡献的人，图灵奖被喻为“计算机界的诺贝尔奖”。

\begin{wrapfigure}{R}{0.3\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.6]{img/Church.eps}
 \captionsetup{labelformat=empty}
 \caption{阿隆佐$\cdot$丘奇（Alonzo Church, 1903 - 1995）}
 \label{fig:Church}
%\end{figure}
\end{wrapfigure}

对计算本身进行形式化，被称为“元数学”。这一试图重新为计算树立数学地位的尝试产生了一个杰作——$\lambda$演算。$\lambda$演算名字的由来还有一则有趣的故事。在研究计算本身时，人们意识到应该区分函数和函数的值，例如我们说“如果$x$是奇数那么$x \times x$也是奇数”，这时我们指的是函数的值，而如果我们说“$x \times x$是递增的”，那说的就是这个函数本身。为了区别这两个概念，我们会把函数写成$x \mapsto x \times x$而不单是$x \times x$。

“$\mapsto$”符号是在1930年前后，由尼古拉$\cdot$布尔巴基（Nicolas Bourbaki）\footnote{“布尔巴基”是一群法国数学家共同使用的笔名。布尔巴基的目的是在集合论的基础上，用最具严格性，最一般的方式来重写整个现代高等数学。布尔巴基学派产生了包括安德烈·韦伊，亨利·嘉当，舒瓦兹，塞尔，格罗滕迪克，迪厄多内等一大批著名数学家。}引入的。二十世纪初，罗素和怀特海在《数学原理》中使用了$\hat{x}(x \times x)$的表示法，1930年代时，丘奇想使用类似的表示法，但是他的出版商不知道如何在$x$上面印出这个“帽子”符号，于是就改成在$x$的前面加上一个与之相似的大写希腊字母$\Lambda$，它后来又变成了小写字母$\lambda$。于是最终表达式就成了今天我们看到的$\lambda x . x \times x$\cite{Dowek2011}。虽然$x \mapsto x \times x$的表示法已经广为接受，人们还是会在逻辑学和计算机科学中使用丘奇的表示法，而这种语言的名字“$\lambda$演算”也正源自于此。

\subsection{表达式化简}
我们先从一些简单的例子开始了解如何用$\lambda$演算形式化算法与计算过程。首先是加减乘除四则运算，我们把它们也看成某种函数。比如加法1+2，可以看作用一个名为“+”的函数，作用到1和2两个变量上。按照把函数名写在前面的习惯，这一表达式可以写成$(+\ 1\ 2)$。针对表达式的求值，就可以看作是一系列的化简过程，例如：

\[
\begin{array}{ll}
    & (+\ (\times\ 2\ 3)\ (\times\ 4\ 5)) \\
\to & (+\ 6\ (\times\ 4\ 5)) \\
\to & (+\ 6\ 20) \\
\to & 26
\end{array}
\]

这里箭头符号$\to$读作“化简为”。注意到函数$f$应用到变量$x$上，并没有写成$f(x)$而是写成了$f\ x$的形式。对于多元函数，如$f(x, y)$，我们不把它写成$(f\ (x, y))$而是用更加简单一致的方法写成$((f\ x)\ y)$。这样为了表达“三加四”这样的加法，需要写成$((+\ 3)\ 4)$。表达式$(+\ 3)$实际上表示了一个函数，它把任何传入的变量都加3。这样在整体上这个表达式的含义就是：把加法“+”函数先应用到变量3上，这样的结果是一个函数，然后再把这个函数应用到变量4上。这样本质上，我们认为所有的函数都只接受一个参数。这一方法最初是由肖芬格尔（Schönfinkel, 1889 - 1942）在1924年提出，后来经哈斯克尔$\cdot$克里在1958年后被广泛使用的。因此它被称为函数的“克里化”（Currying）\cite{SPJ1987}。

严格按照克里化的方式写出的表达式含有很多括弧，为了简化描述，我们在不引起歧义的情况下会省略一些括弧，例如将$((f\ ((+\ 3)\ 4))\ (g\ x))$简写为$(f\ (+\ 3\ 4)\ (g\ x))$。

在进行表达式化简时，需要能够理解一些基本含义并做出计算。对于四则运算，我们已经在第一章中介绍的皮亚诺算术的基础上定义了加法和乘法。我们也可以用类似的方式定义其逆运算减法和除法。对于参与运算以及表示结果的常数，我们也有基于零和后继的定义。在这些理论基础上，实现时通常将基本运算和数字内置实现（built-in）以提高性能。通常加以内置实现的还有与或非等逻辑运算、布尔常量真(true)和假(false)。条件表达式可以按照第一章描述的麦卡锡形式$(p \mapsto f, g)$实现，也可以定义为下面的if形式。

\[
\begin{array}{llcl}
\textbf{if}\ true\! & \textbf{then}\ e_t\ \textbf{else}\ e_f & \mapsto & e_t \\
\textbf{if}\ false\! & \textbf{then}\ e_t\ \textbf{else}\ e_f & \mapsto & e_f
\end{array}
\]

其中$e_t$和$e_f$都是表达式。第一章中通过$cons$定义的复合数据结构，也可以通过函数来抽取其中的各个部分：

\[
\begin{array}{l}
head\ (cons\ a\ b) \mapsto a \\
tail\ (cons\ a\ b) \mapsto b
\end{array}
\]

\subsection{$\lambda$抽象}

我们前面简单介绍了$\lambda$符号的由来，所谓$\lambda$抽象，实际上是一种构建函数的方法。我们通过一个例子来了解$\lambda$抽象的各个组成部分。

\[
(\lambda x . +\ x\ 1)
\]

一个$\lambda$抽象包含四个组成部分，首先是$\lambda$符号，表示“接下来要定义一个函数”。紧随其后的是变量，在本例中就是$x$，被称为形参（formal parameter）。形参之后是一个点，剩余部分是函数体，它向右延申到最长，在本例中是$+\ x\ 1$。有时为了避免对函数体的右边界产生歧义，可以增加括号，对于本例，可以写成：$(+\ x\ 1)$。为了记忆方便，我们可以将$\lambda$抽象的四个部分按照如下方法对应到自然语言上。

\begin{tabular}{cccc}
($\lambda$ & $x$ & . & +\  $x$\ 1) \\
$\uparrow$ & $\uparrow$ & $\uparrow$ & $\uparrow$ \\
函数的 & 自变量是$x$ & 它 & 将$x$和1相加 \\
\end{tabular}

为了方便，在后继的推导中我们也会等价地使用$x \mapsto x + 1$形式的记法。这里有一点需要澄清，$\lambda$抽象并不等同于$\lambda$表达式。$\lambda$抽象只是$\lambda$表达式的一种情况，$\lambda$表达式还包括其它三种情况：

\begin{tabular}{rcll}
<表达式> & = & <常量> & 内置的常量，数字、布尔值等 \\
        & | & <变量> & 变量名 \\
        & | & <表达式> <表达式> & 应用 \\
        & | & $\lambda$ <变量> . <表达式> & $\lambda$抽象
\end{tabular}

\subsection{$\lambda$变换规则}

考虑下面的$\lambda$表达式，如果对它化简，我们需要知道“全局”变量$y$的值。与之相对，我们不需要事先知道变量$x$的值，因为它以形参出现在函数中。

\[
(\lambda x . +\ x\ y)\ 2
\]

比较$x$和$y$的不同之处，我们称$x$是被$\lambda x$“绑定”的。当将这一$\lambda$抽象应用到参数2时，我们会用2替换掉所有的$x$。相反，$y$没有被$\lambda$绑定，我们称变量$y$是自由的。总之，表达式的值是由未被绑定的自由变量的值决定的。一个变量要么是被绑定的，要么是自由的。下面是一个稍复杂点的例子：

\[
\lambda x . +\ ((\lambda y . +\ y\ z)\ 3)\ x
\]

我们可以把它写成箭头记法，这样可以看得更清楚：

\[
x \mapsto ((y \mapsto y + z)\ 3) + x
\]

这样就可以看出，$x$与$y$是被绑定的，而$z$是自由变量。在更加复杂的表达式中，同一变量的名字，有时是被绑定的，有时又以自由变量的形式出现，例如：

\[
+\ x\ ((\lambda x . +\ x\ 1)\ 2)
\]

写成箭头形式为：

\[
x + ((x \mapsto x + 1)\ 2)
\]

我们看到，第一次出现的$x$是个自由变量，而后面出现的$x$是被绑定的。在复杂的表达式中，这种同一名字代表不同的变量的情况给会表达式化简带来麻烦。为了解决名称冲突的问题，我们引入第一条$\lambda$变换规则——$\alpha$-变换。其中$\alpha$是希腊字母阿尔法。这一规则说，我们可以将$\lambda$表达式中的一个变量，重新命名为另一个变量。例如：

\[
\lambda x . +\ x\ 1 \quad \overset{\alpha}{\longleftrightarrow} \quad \lambda y . +\ y\ 1
\]

%for short arrow, can be replaced with \xleftrightarrow{\alpha}

写成箭头形式为：

\[
x \mapsto x + 1 \quad \overset{\alpha}{\longleftrightarrow} \quad y \mapsto y + 1
\]

我们说$\lambda$抽象是一种构建函数的方法，如何将构建好的函数应用到参数值上呢？这就需要引入第二条$\lambda$变换规则——$\beta$-变换。正向使用这条规则时，把$\lambda$抽象函数体中的所有形参的自由出现替换成形参的值。例如：

\[
(x \mapsto x + 1)\ 2
\]

根据变换规则，把$\lambda$抽象$x \mapsto x + 1$应用到自变量2上得2 + 1。即2 + 1是将函数体$x + 1$中出现的形参$x$替换为2的结果。用箭头将这一变换表示为：

\[
(x \mapsto x + 1)\ 2 \quad \overset{\beta}{\longrightarrow} \quad 2 + 1
\]

我们称这一特定箭头方向的变换为$\beta$-规约（$\beta$-reduction）\footnote{也称为$\beta$-消解或$\beta$-化简}。而反向使用这条规则称为$\beta$-抽象。下面再通过更多的列子了解一下$\beta$-规约。首先是形参多次出现的例子：

\[
\begin{array}{rcl}
(x \mapsto x \times x)\ 2 & \overset{\beta}{\longrightarrow} & 2 \times 2 \\
                          & \longrightarrow & 4 \\
\end{array}
\]

然后是形参出现零次的情况：

\[
(x \mapsto 1)\ 2 \quad \overset{\beta}{\longrightarrow} \quad 1
\]

这是一个典型的“常量映射”的例子。接下来是一个多重规约的例子：

\[
\begin{array}{rcll}
(x \mapsto (y \mapsto y - x))\ 2\ 4\ & \overset{\beta}{\longrightarrow} & (y \mapsto y - 2)\ 4 & \text{克里化} \\
                                     & \overset{\beta}{\longrightarrow} & 4 - 2 & \text{内层规约} \\
                                     & \longrightarrow & 1 & \text{内置四则运算}
\end{array}
\]

可以看到，从外向内逐层规约是一个不断克里化的过程。有时我们把多重规约简写如下：

\[
(\lambda x . (\lambda y . E)) \quad \Rightarrow \quad (\lambda x . \lambda y . E)
\]

其中$E$表示函数体。写成箭头形式为：

\[
(x \mapsto (y \mapsto E)) \quad \Rightarrow \quad (x \mapsto y \mapsto E)
\]

使用$\beta$-规约进行函数应用时，参数也可以是另一个函数，例如：

\[
\begin{array}{rcl}
(f \mapsto f\ 5)\ (x \mapsto x + 1) & \overset{\beta}{\longrightarrow} & (x \mapsto x + 1)\ 5 \\
                                    & \overset{\beta}{\longrightarrow} & 5 + 1 \\
                                    & \longrightarrow & 6
\end{array}
\]

最后一个我们要介绍的变换是$\eta$-变换。它的定义如下：

\[
(\lambda x . F\ x) \quad \overset{\eta}{\longleftrightarrow} \quad F
\]

写成箭头形式为：

\[
x \mapsto F\ x \quad \overset{\eta}{\longleftrightarrow} \quad F
\]

其中$F$是函数，且$x$不是$F$中的自由变量。我们来看一个例子：

\[
(\lambda x . +\ 1\ x) \quad \overset{\eta}{\longleftrightarrow} \quad (+\ 1)
\]

在这个例子中，$\eta$-变换两边的行为表现得完全一样。如果应用到一个参数上，效果都是把这个参数增加1。$\eta$-变换之所以要求$x$不能是$F$的自由变量是为了避免错误地将$(\lambda x. +\ x\ x)$变换为$(+\ x)$。我们可以看到，$x$是$(+\ x)$中的自由变量。同样，限定$F$必须为函数是为了避免错误地将1变换为$(\lambda x . 1\ x)$。在上面的定义中，称从左向右的变换为$\eta$-规约。

至此，我们介绍了$\lambda$表达式变换的三大规则，我们小结一下。

\begin{enumerate}
\item $\alpha$-变换用于改变形参的名字；
\item $\beta$-规约用于实现函数应用；
\item $\eta$-规约用于去除多余的$\lambda$抽象。
\end{enumerate}

此外，我们称内置函数的化简，如加减乘除四则运算、逻辑上的与或非等为$\delta$-变换。在某些文献上，还会看到另外一种$\lambda$表达式变换的简记形式，我们这里简单介绍一下。对表达式$(\lambda x. E)\ M$，进行$\beta$-规约时，我们用$M$替换$E$中的$x$，将此结果记为$E[M/x]$。这样三大变换就可以简写成下面的形式：

\begin{tabular}{|l|rcl|rcl|}
\hline
变换 & \multicolumn{3}{|c|}{$\lambda$形式} & \multicolumn{3}{|c|}{箭头形式} \\
\hline
$\alpha$ & $(\lambda x . E)$ & $\overset{\alpha}{\longleftrightarrow}$ & $\lambda y . E[y/x]$
         & $x \mapsto E$ & $\overset{\alpha}{\longleftrightarrow}$ & $y \mapsto E[y/x]$ \\
\hline
$\beta$  & $(\lambda x . E)\ M$ & $\overset{\beta}{\longleftrightarrow}$ & $E[M/x]$
         & $(x \mapsto E)\ M$ & $\overset{\beta}{\longleftrightarrow}$ & $E[M/x]$ \\
\hline
$\eta$   & $(\lambda x . E\ x)$ & $\overset{\eta}{\longleftrightarrow}$ & $E$
         & $x \mapsto E\ x$ & $\overset{\eta}{\longleftrightarrow}$ & $E$ \\
\hline
\end{tabular}

由于这些转换规则都是双向的，在对一个$\lambda$表达式进行变换时，既可以从左向右进行规约，也可以反过来从右向左进行抽象。这样自然会产生两个问题。第一个问题是，化简过程最终会停止么？第二个问题是，不同的化简方式得到的结果是一致的么？对于第一个问题，答案是不确定的，化简过程不能保证一定会中止\footnote{注意答案并不是“否定”，而是不确定。这本质上和图灵停机问题是一致的。即不存在一个可判定过程，确定任意化简是否中止。我们在最后一章会详细讨论这个问题。}。下面就是一个“死循环”的例子：$(D\ D)$，其中$D$定义为$\lambda x. x\ x$，写成箭头形式为$x \mapsto x\ x$。如果我们试图化简，就会得到这样的结果：

\[
\begin{array}{rcll}
(D\ D) & \to & (x \mapsto x\ x)\ (x \mapsto x\ x) & \text{代入$D$的定义} \\
       & \xrightarrow{\alpha} & (x \mapsto x\ x)\ (y \mapsto y\ y) & \text{对第二个$\lambda$抽象用$\alpha$-变换} \\
       & \xrightarrow{\beta} & (y \mapsto y\ y)\ (y \mapsto y\ y) & \text{用第二个表达式替换$x$} \\
       & \xrightarrow{\alpha} & (x \mapsto x\ x)\ (x \mapsto x\ x) & \text{再用$x$替换回$y$} \\
       & \to & (x \mapsto x\ x)\ (x \mapsto x\ x) & \text{重复使用上述步骤} \\
       & ... &
\end{array}
\]

\begin{wrapfigure}{R}{0.3\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.3]{img/Church-Rosser.eps}
 %\captionsetup{labelformat=empty}
 \caption{丘奇-罗瑟定理的示意}
 \label{fig:Church-Rosser-confluence}
%\end{figure}
\end{wrapfigure}

更耐人寻味的是这个例子：$(\lambda x . 1)\ (D\ D)$，如果先化简$(\lambda x . 1)$，那么化简过程会中止，答案为1。反之如果先化简$(D\ D)$，则根据上面的结论，这一过程就会陷入“死循环”而无法中止。丘奇和他的学生罗瑟\footnote{罗瑟（John Barkley Rosser Sr. 1907 - 1989）是美国数学家、逻辑学家。除了丘奇-罗瑟定理外，罗瑟还和克莱尼一起还提出了克莱尼-罗瑟悖论，在数论领域，他提出了罗瑟筛法，并证明了罗瑟定理，该定理指出，第$n$个素数$p_n > n \ln n$。罗瑟在1936年还给出了一种更强的哥德尔第一不完全定理的形式，他把不可判定命题改进为：“对本命题的任何证明，都存在一个对否命题的更短证明。”}在1936年证明了一对定理，完整地回答了第二个问题。

\begin{theorem}[丘奇-罗瑟定理一]
若$E_1 \leftrightarrow E_2$，则存在$E$，使得$E_1 \to E$且$E_2 \to E$。
\end{theorem}

也就是说，如果化简过程是可终止的，则化简结果是一致的。不同的化简方法会化简到同一结果，如图\ref{fig:Church-Rosser-confluence}所示。在此基础上，丘奇和罗瑟又证明了第二定理。为此我们先要给出“范式”（Normal form）的概念，所谓范式，又称$\beta$范式，是指不能再进行$\beta$-规约的形式。简单来讲，就是表达式中能够应用的函数都已经应用了。更严格的范式是$\beta-\eta$范式，在这样的范式中，既不能进行$\beta$-规约，也不能进行$\eta$-规约。例如$(x \mapsto x + 1)\ y$不是范式，因为它可以进行$\beta$-规约变成$y + 1$。下面是范式的递归定义。

\[
\begin{array}{rcll}
normal((\lambda x . y)\ z) & = & \textbf{false} & \text{可进一步$\beta$-规约} \\
normal(\lambda x . (f\ x)) & = & \textbf{false} & \text{可进一步$\eta$-规约} \\
normal(x\ y) & = & normal(x) \land normal(y) & \text{应用：函数和参数都是范式} \\
normal(x) & = & \textbf{true} & \text{其它情况}
\end{array}
\]

\begin{theorem}[丘奇-罗瑟定理二]
若$E_1 \to E_2$，且$E_2$为范式，则存在从$E_1$化简到$E_2$的正规顺序。
\end{theorem}

注意，这一定理要求化简过程也必须是可终止的。所谓正规顺序（normal order）就是从左向右，从外向内的化简顺序。

\section{递归的定义}

利用上一节中介绍的$\lambda$抽象，我们已经可以定义一些简单函数，但是如何定义递归函数呢？比如阶乘，它可以递归地定义为：

\[
fact = n \mapsto \textbf{if}\ n = 0\ \textbf{then}\ 1\ \textbf{else}\ n \times fact (n - 1)
\]

但这并不是一个合法的$\lambda$表达式，问题是由于$\lambda$抽象只定义了匿名函数，而我们并未定义如何给函数命名。再次观察递归的阶乘定义，它形如:

\[
fact = n \mapsto (... fact ...)
\]

我们反向使用$\beta$-规约（即$\beta$-抽象），将其变换为：

\[
fact = (f \mapsto (n \mapsto (... f ...)))\ fact
\]

进一步可以抽象为

\be
fact = H\ fact
\label{eq:H-fact}
\ee

其中

\[
H = f \mapsto (n \mapsto (... f ...))
\]

注意到，经过这样的变换，我们得到的$H$不再是递归的，它是一个普通的$\lambda$表达式。观察式(\ref{eq:H-fact})，它表示了递归。在形式上它是一个数学方程，让我们联想起“微分方程”的概念。例如解微分方程$y' = sin(x)$得到$y = a - cos(x)$。如果我们能将方程$F = H\ F$解出，就能完整地定义阶乘了。进一步观察，我们发现这个方程的含义是，将$H$应用到$F$上，得到的结果仍然是$F$。这一概念在数学上叫做“不动点”。我们称$F$是$H$的不动点。再举一个不动点的例子：$\lambda$表达式$x \mapsto x \times x$的不动点是0和1，这是因为$(x \mapsto x \times x)\ 0 = 0$且$(x \mapsto x \times x)\ 1 = 1$。

\subsection{Y组合子}

我们希望找到$H$的不动点，显然$H$的不动点只依赖于$H$本身。为此，我们引入一个函数$Y$，它接受一个函数，然后返回这个函数的不动点。$Y$的行为表现如下：

\be
Y\ H = H\ (Y\ H)
\label{eq:Y-H}
\ee

为此$Y$被称为“不动点组合子”（fixpoint combinator）。使用$Y$，我们就得到了方程(\ref{eq:H-fact})的解：

\be
fact = Y\ H
\label{eq:fact-in-Y}
\ee

这样得到的$fact$是一个无递归的定义。我们可以这样验证这个解：

\[
\begin{array}{rcll}
fact & = & Y\ H & \text{式(\ref{eq:fact-in-Y})} \\
     & = & H\ (Y\ H) & \text{式(\ref{eq:Y-H})} \\
     & = & H\ fact & \text{式(\ref{eq:fact-in-Y})反向}
\end{array}
\]

$Y$的强大之处在于它可以表达所有的递归函数。但是现在的$Y$仍然是个黑盒子，我们需要用$\lambda$抽象来真正实现它。下面就是$Y$的实现：

\be
Y = \lambda h . (\lambda x . h\ (x\ x))\ (\lambda x . h\ (x\ x))
\ee

写成箭头形式为：

\[
Y = h \mapsto (x \mapsto h\ (x\ x)) (x \mapsto h\ (x\ x))
\]

我们打开了潘多拉的魔盒，现在来验证一下这个$Y$的$\lambda$抽象是否表现得符合我们的预期：$Y\ H = H\ (Y\ H)$。

\begin{proof}
\[
\begin{array}{rcll}
Y\ H & = & (h \mapsto (x \mapsto h\ (x\ x)) (x \mapsto h\ (x\ x)))\ H & \text{$Y$的定义} \\
     & \xleftrightarrow{\beta} & (x \mapsto H\ (x\ x))\ (x \mapsto H\ (x\ x)) & \text{$\beta$-规约，用$H$代换$h$} \\
     & \xleftrightarrow{\alpha} & (y \mapsto H\ (y\ y))\ (x \mapsto H\ (x\ x)) & \text{对前半部分用$\alpha$-变换} \\
     & \xleftrightarrow{\beta} & H\ ((x \mapsto H\ (x\ x))\ (x \mapsto H\ (x\ x))) & \text{$\beta$-规约，$y$被后半部代换} \\
     & \xleftrightarrow{\beta} & H\ (h \mapsto (x \mapsto h\ (x\ x))\ (x \mapsto h\ (x\ x))\ H) & \text{$\beta$-抽象，$H$抽出为参数} \\
     & = & H\ (Y\ H) & \text{代入$Y$的定义}
\end{array}
\]
\end{proof}

最终，使用$Y$，我们可以如下实现阶乘的定义：

\[
Y\ (f \mapsto (n \mapsto \textbf{if}\ n = 0\ \textbf{then}\ 1\ \textbf{else}\ n \times f\ (n - 1)))
\]

用$\lambda$-抽象来定义$Y$的数学意义远大于其实现的意义。在真实的环境中，通常$Y$被内置实现为函数，可以直接将$Y\ H$转化为$H\ (Y\ H)$。

\section{$\lambda$演算的意义}

$\lambda$演算的意义在于，它用一组简单的规则对复杂的计算过程进行了定义。将欧几里得算法用$\lambda$表示出来，再利用$\beta$规约进行计算。这样的实现可能比较复杂，但确实可行。它不仅可以表达这一函数，而是对所有的可计算函数都使用。图灵后来证明了$\lambda$演算与图灵机的等价性。$\lambda$演算的一大优势在于它仅仅使用了传统的数学概念——函数。因而在十九世纪30年代，$\lambda$演算被用来对数学进行形式化。然而在1935年，克莱尼-罗瑟悖论证明了最初的$\lambda$形式系统在逻辑上是不一致的。1936年，丘奇将$\lambda$演算模型中和纯计算有关的部分分离出来，称为的无类型$\lambda$演算。1940年时，丘奇又提出了一个弱化计算，但是逻辑自洽的形式系统，被称之为简单类型$\lambda$演算。

我们展示了如何用$\lambda$演算定义基本的四则运算、逻辑运算、定义和应用普通函数以及递归函数。最后，我们给出如何用$\lambda$演算定义复合数据结构。我们用此前定义的$cons$、$head$、$tail$作为例子。以下是它们的$\lambda$抽象定义：

\[
\begin{array}{rcl}
cons & = & (\lambda a . \lambda b . \lambda f . f\ a\ b) \\
head & = & (\lambda c . c\ (\lambda a . \lambda b . a)) \\
tail & = & (\lambda c . c\ (\lambda a . \lambda b . b))
\end{array}
\]

写成箭头形式为：

\[
\begin{array}{rcl}
cons & = & a \mapsto b \mapsto f \mapsto f\ a\ b \\
head & = & c \mapsto c\ (a \mapsto b \mapsto a) \\
tail & = & c \mapsto c\ (a \mapsto b \mapsto b)
\end{array}
\]

我们来验证一下$head\ (cons\ p\ q) = p$这一关系。

\[
\begin{array}{rcl}
head\ (cons\ p\ q) & = & (c \mapsto c\ (a \mapsto b \mapsto a))\ (cons\ p\ q) \\
                   & \xrightarrow{\beta} & (cons\ p\ q)\ (a \mapsto b \mapsto a) \\
                   & = & ((a \mapsto b \mapsto f \mapsto f\ a\ b)\ p\ q)\ (a \mapsto b \mapsto a) \\
                   & \xrightarrow{\beta} & ((b \mapsto f \mapsto f\ p\ b)\ q)\ (a \mapsto b \mapsto a) \\
                   & \xrightarrow{\beta} & (f \mapsto f \mapsto f\ p\ q)\ (a \mapsto b \mapsto a) \\
                   & \xrightarrow{\beta} & (a \mapsto b \mapsto a)\ p\ q \\
                   & \xrightarrow{\beta} & (b \mapsto p)\ q \\
                   & \xrightarrow{\beta} & p
\end{array}
\]

这说明，理论上复合数据结构不必一定要内置实现，而可以用$\lambda$定义。本章练习中还展示了如何用$\lambda$演算基于皮亚诺公理系统定义自然数、布尔值及逻辑运算。

\begin{Exercise}
\Question{使用$\lambda$变换规则验证$tail\ (cons\ p\ q) = q$。}
\Question{可以仅仅使用$\lambda$演算来定义自然数。下面是丘奇数的定义：
\[
\begin{array}{r@{\quad:\quad}l}
0 & \lambda f . \lambda x . x \\
1 & \lambda f . \lambda x . f\ x \\
2 & \lambda f . \lambda x . f\ (f\ x) \\
3 & \lambda f . \lambda x . f\ (f\ (f\ x)) \\
  & ...
\end{array}
\]
请利用第一章介绍的内容，定义丘奇数的加法和乘法。
}
\Question{以下是丘奇布尔值的定义，以及逻辑运算的一种实现：
\[
\begin{array}{r@{\quad:\quad}l}
\textbf{true} & \lambda x . \lambda y . x \\
\textbf{false} & \lambda x . \lambda y . y \\
\textbf{and} & \lambda p . \lambda q . p\ q\ p \\
\textbf{or} & \lambda p . \lambda q . p\ p\ q \\
\textbf{not} & \lambda p . p\ \textbf{false}\ \textbf{true}
\end{array}
\]
其中\textbf{false}的定义和丘奇数0的定义本质上是相同的。试用$\lambda$变换证明：\textbf{and}\ \textbf{true}\ \textbf{false} = \textbf{false}；你能给出if...then...else...语句的$\lambda$定义么？
}
\end{Exercise}

\section{更多的递归结构}

至此，我们已经将递归函数和递归数据结构建立在完整的数学基础上。利用这些工具，我们可以继续定义一些较复杂的数据结构。例如下面的二叉树。

\lstset{frame=none}
\begin{lstlisting}
data Tree A = nil | node (Tree A, A, Tree A)
\end{lstlisting}

这个递归定义说，一棵元素类型为A的二叉树或者为空，或者是一个分支节点。节点包含三部分：两棵元素类型为A的子树和一个类型为A的元素。习惯上我们称这两棵子树为左子树和右子树。A是类型参数，例如自然数。$node(nil, 0, node(nil, 1, nil))$表示了一棵元素为自然数的二叉树。下面我们为二叉树定义抽象的叠加操作$foldt$。

\be
\begin{array}{l}
foldt(f, g, c, nil) = c \\
foldt(f, g, c, node(l, x, r)) = g(foldt(f, g, c, l), f(x), foldt(f, g, c, r))
\end{array}
\ee

如果函数$f$将类型为A的自变量映射为类型为B的值，我们将其类型记为$f : A \to B$。克里化的函数$foldt(f, g, c)$的类型为$foldt(f, g, c) : Tree\ A \to B$，其中$c$的类型为$B$，而函数$g$的类型为$g : (B \times B \times B) \to B$，写成克里化的形式为$g : B \to B \to B \to B$。使用抽象的叠加函数$foldt$我们可以定义针对二叉树的逐一映射$mapt$：

\be
mapt(f) = foldt(f, node, nil)
\ee

通过叠加操作，还可以定义函数来统计一棵二叉树中的元素个数：

\be
sizet = foldt(one, sum, 0)
\ee

其中$one(x) = 1$，是一个常数函数，它对任何变量都返回1。$sum$是一个三元的累加函数：$sum(a, b, c) = a + b + c$。

在此基础上，复合使用第一章定义的列表，我们还可以从二叉树扩展到多叉树，下面是一个多叉树的定义：

\begin{lstlisting}
data MTree A = nil | node (A, List (MTree A))
\end{lstlisting}

一棵元素类型为A的多叉树或者为空，或者为一个复合节点。复合节点包括一个类型为A的元素，和若干子树。所有子树用一个多叉树的列表来表示。定义多叉树的抽象叠加操作需要相互递归调用列表的叠加操作。

\be
\begin{array}{l}
foldm(f, g, c, nil) = c \\
foldm(f, g, c, node(x, ts)) = foldr(g(f(x), c), h, ts) \\
h(t, z) = foldm(f, g, z, t)
\end{array}
\ee

\begin{Exercise}
\Question{不用抽象的叠加操作$foldt$，通过递归定义二叉树的逐一映射$mapt$；}
\Question{定义一个函数$depth$，计算一棵二叉树的最大深度；}
\Question{有人认为，二叉树的抽象叠加操作$foldt$应该这样定义：
\[
\begin{array}{l}
foldt(f, g, c, nil) = c \\
foldt(f, g, c, node(l, x, r)) = foldt(f, g, g(foldt(f, g, c, l), f(x)), r)
\end{array}
\]
也就是说，$g : (B \times B) \to B$是一个类似于加法这样的二元函数。能否利用这个$foldt$定义逐一映射$mapt$？}
\Question{排序二叉树（又称二叉搜索树）是一种特殊的二叉树，如果二叉树的元素类型A是可比较的，并且对任何非空节点$node(l, k, r)$都满足：左子树$l$中的任何元素都小于$k$，右子树$r$中的任何元素都大于$k$。定义二叉树的插入函数$insert(x, t) : (A \times Tree A) \to Tree A$}
\Question{为多叉树定义逐一映射。能否利用多叉树的叠加操作来定义？如果不能，应当怎样修改叠加操作？}
\end{Exercise}

\section{递归的形式与结构}

递归不仅存在于古老的欧几里得算法和现代计算机系统中，它迷人的形式和结构还出现在各种人类文明艺术中。图\ref{fig:Ceramic-Tile-Tessellations-Marrakech}的平面镶嵌中，可以看到多重不同的递归形式。

%\begin{wrapfigure}{R}{0.3\textwidth}
\begin{figure}[htbp]
 \centering
 \includegraphics[scale=1]{img/Marrakech.eps}
 %\captionsetup{labelformat=empty}
 \caption{马拉喀什（摩洛哥城市）的瓷砖图案}
 \label{fig:Ceramic-Tile-Tessellations-Marrakech}
\end{figure}
%\end{wrapfigure}

我们可以看到瓷砖中的多边形图案中递归地含有更小的多边形嵌套。通过不同颜色的瓷砖，这种递归展现出几何形式的美。这些图案还在更大的范围组成条纹形式，而各个条纹内部都是不同的递归图形。图\ref{fig:flower}左边展示的是文艺复兴时期艺术大师达$\cdot$芬奇手稿中的递归图样。在圆周上使用相同的半径，依次可作出六个相互交织的圆，从而构成一个六瓣的花样图案。而在更大的范围上，又递归地构成了同样形式的图案。左侧是中国民间手工编织的蝈蝈笼子，他们展示了类似的递归图样。笼子的网眼是六边形的，而笼子的整体形状从轴向看去也是六边形的。

%\begin{wrapfigure}{R}{0.3\textwidth}
\begin{figure}[htbp]
 \centering
 \subcaptionbox{达芬奇绘制的递归图案手稿}[0.3\linewidth]{\includegraphics[scale=0.20]{img/ldv_flower.eps}} \quad
 \subcaptionbox{手工编织的蝈蝈笼子}[0.5\linewidth]{\includegraphics[scale=0.36]{img/cage.eps}}
 %\captionsetup{labelformat=empty}
 \caption{艺术和生活物品中的递归形式}
 \label{fig:flower}
\end{figure}
%\end{wrapfigure}

递归不仅出现在美术作品中，还出现在更加抽象的艺术形式中，例如音乐。复调音乐中的卡农（Canon）和赋格（Fugue）都是这方面的代表。卡农的所有声部虽然都模仿一个声部，但不同高度的声部依一定间隔进入，造成一种此起彼伏，连绵不断的效果。每一个声部都地归地展示主题但却含有各种变化，比如音调的升高或降低、逆行重叠、速度变快（减值）或变慢（增值）、旋律倒影等等。

\begin{wrapfigure}{L}{0.45\textwidth}
%\begin{figure}[htbp]
 \centering
 \includegraphics[scale=0.6]{img/Drawing-Hands-1948.eps}
 %\captionsetup{labelformat=empty}
 \caption{艾舍尔的作品《画手》，1948年}
 \label{fig:Drawing-Hands}
%\end{figure}
\end{wrapfigure}

赋格通常建立在一个主题上，以不同的声部、不同的调子、偶尔也用不同的速度或上下颠倒或从后往前地进行演奏。然而，赋格的概念远不如卡农那么严格，因而允许有更多的情感或艺术的表现。赋格的识别标志的是它的开始方式：单独的一个声部唱出它的主题，唱完后，第二个声部或移高五度或降低四度进入。与此同时，第一个声部继续唱“对应主题”，也叫第二主题，用来在节奏、和声、及旋律方面与主题形成对比。每个声部依次唱出主题，常常是另一个声部伴唱对应主题，其它的声部所起的作用随作曲家的想象而定。当所有的声部都“到齐”了，就不再有什么规则了。当然，还是有一些标准的手法，但它没有严格到只能够按照某个公式去创作赋格。 《音乐的奉献》 中的两首赋格曲就是杰出例子，它们绝不可能“照公式创造出来”。这两首曲子都具有远比赋格的性质更为深刻的东西\cite{GEB}。

这些都是有限递归的例子。图\ref{fig:Drawing-Hands}是荷兰艺术大师艾舍尔在1948年创作的《画手》，两只手递归地在描绘着对方。《画手》是无穷递归的典型例子。画中上方的手正在用一支笔描绘着下方的手，而下方的手也在地归地描绘着上方的手。这组相互递归的嵌套一层一层，无穷无尽。

无穷递归的一个数学与艺术完美结合的例子是“分形”（fractal）。例如著名的分形图案“科克雪花”（Kock snowflake）曲线可以通过这样的无穷递归规则来产生：对图形中的每个线段，均分为三段，以第二段为底向上方作出一个等腰三角形，然后再把这个底擦掉。图\ref{fig:fractal}中展示了三重递归后从一个正三角形得到的科克雪花。另一个著名的递归分形图案是谢尔平斯基三角形（Sierpinski），它的生成规则是对图形中的每个三角形，分别取三边的中点，然后连成一个内部的小三角形。下图展示了递归四次后的谢尔平斯基三角形。

%\begin{wrapfigure}{R}{0.3\textwidth}
\begin{figure}[htbp]
 \centering
 \subcaptionbox{科克雪花的递归生成规则}[0.4\linewidth]{\includegraphics[scale=0.25]{img/KochFlake.eps}}
 \subcaptionbox{谢尔平斯基三角形}[0.4\linewidth]{\includegraphics[scale=0.1]{img/Sierpinski-triangle.eps}}
 %\captionsetup{labelformat=empty}
 \caption{递归产生的分形图案}
 \label{fig:fractal}
\end{figure}
%\end{wrapfigure}

最后让我们以两张分形图案来结束本章，其中一张是人类思维产生的分形——茱莉亚集（Julia）；另一张是自然界产生的分形。

\begin{figure}[htbp]
 \centering
 \subcaptionbox{茱莉亚集分形}[0.45\linewidth]{\includegraphics[scale=0.18]{img/Julia_set.eps}}
 \subcaptionbox{西兰花中的分形}[0.45\linewidth]{\includegraphics[scale=0.2]{img/Broccoli.eps}}
 %\captionsetup{labelformat=empty}
 \caption{人类思维和自然界产生的分形}
 \label{fig:more-fractal}
\end{figure}

\section{扩展阅读}

韩雪涛的《数学悖论与三次数学危机》\cite{HanXueTao16}对古希腊数学的成就有生动的介绍。欧几里得的《几何原本》中译本\cite{Elements}是永远的经典。斯捷潘诺夫和罗斯的《数学与泛型编程》\cite{StepanovRose15}中有欧几里得算法算法的多种实现。随着各大主流编程环境引入lambda演算，这方面的介绍材料很多。佩顿琼斯的《函数式编程语言的实现》\cite{SPJ1987}讲解全面并且深入浅出。侯世达先生的《集异璧》\cite{GEB}中有大量关于递归的介绍和奇思妙想，曾获得普利策大奖。中译本秉着文化同构的精神进行了非凡的再创作。

\ifx\wholebook\relax \else
\begin{thebibliography}{99}

\bibitem{HanXueTao16}
韩雪涛 ``数学悖论与三次数学危机''. 人民邮电出版社. 2016, ISBN: 9787115430434

\bibitem{StepanovRose15}
[美] 亚历山大 A$\cdot$斯捷潘诺夫，丹尼尔 E$\cdot$罗斯著，爱飞翔译. ``数学与泛型编程：高效编程的奥秘''. 机械工业出版社. 2017, ISBN: 9787111576587

\bibitem{Elements}
[古希腊] 欧几里得 著，兰纪正 朱恩宽 译，梁宗巨 张毓新 徐伯谦 校订 ``几何原本''. 译林出版社. 2014, ISBN: 9787544750066

\bibitem{HanXueTao2009}
韩雪涛 ``好的数学——“下金蛋”的数学问题''. 湖南科学技术出版社. 2009, ISBN: 9787535756725

\bibitem{Bezout-Identity}
Wikipedia ``贝祖等式'' \url{https://en.wikipedia.org/wiki/Bézout's_identity}

\bibitem{LiuXinyu2017}
刘新宇 ``算法新解'' 人民邮电出版社. 2017, ISBN: 9787115440358

\bibitem{wiki-Turing}
Wikipedia ``艾伦$\cdot$图灵'' \url{https://en.wikipedia.org/wiki/Alan_Turing}

\bibitem{Dowek2011}
[法] 吉尔$\cdot$多维克 著，劳佳 译 ``计算进化史：改变数学的命运''. 人民邮电出版社. 2017, ISBN: 9787115447579

\bibitem{SPJ1987}
Simon L. Peyton Jones. ``The implementation of functional programming language''. Prentice Hall. 1987, ISBN: 013453333X

\bibitem{GEB}
[美]候世达 ``哥德尔、埃舍尔、巴赫——集异壁之大成''. 商务印书馆 1996. ISBN: 978-7-100-01323-9

\end{thebibliography}

\expandafter\enddocument
%\end{document}

\fi
